// Copyright 2019 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/objects/string.h"

#include "src/char-predicates.h"
#include "src/conversions.h"
#include "src/handles-inl.h"
#include "src/heap/heap-inl.h" // For LooksValid implementation.
#include "src/objects/map.h"
#include "src/objects/oddball.h"
#include "src/objects/string-comparator.h"
#include "src/objects/string-inl.h"
#include "src/ostreams.h"
#include "src/string-builder-inl.h"
#include "src/string-hasher.h"
#include "src/string-search.h"
#include "src/string-stream.h"
#include "src/unicode-inl.h"

namespace v8 {
namespace internal {

    Handle<String> String::SlowFlatten(Isolate* isolate, Handle<ConsString> cons,
        AllocationType allocation)
    {
        DCHECK_NE(cons->second()->length(), 0);

        // TurboFan can create cons strings with empty first parts.
        while (cons->first()->length() == 0) {
            // We do not want to call this function recursively. Therefore we call
            // String::Flatten only in those cases where String::SlowFlatten is not
            // called again.
            if (cons->second()->IsConsString() && !cons->second()->IsFlat()) {
                cons = handle(ConsString::cast(cons->second()), isolate);
            } else {
                return String::Flatten(isolate, handle(cons->second(), isolate));
            }
        }

        DCHECK(AllowHeapAllocation::IsAllowed());
        int length = cons->length();
        allocation = ObjectInYoungGeneration(*cons) ? allocation : AllocationType::kOld;
        Handle<SeqString> result;
        if (cons->IsOneByteRepresentation()) {
            Handle<SeqOneByteString> flat = isolate->factory()
                                                ->NewRawOneByteString(length, allocation)
                                                .ToHandleChecked();
            DisallowHeapAllocation no_gc;
            WriteToFlat(*cons, flat->GetChars(no_gc), 0, length);
            result = flat;
        } else {
            Handle<SeqTwoByteString> flat = isolate->factory()
                                                ->NewRawTwoByteString(length, allocation)
                                                .ToHandleChecked();
            DisallowHeapAllocation no_gc;
            WriteToFlat(*cons, flat->GetChars(no_gc), 0, length);
            result = flat;
        }
        cons->set_first(isolate, *result);
        cons->set_second(isolate, ReadOnlyRoots(isolate).empty_string());
        DCHECK(result->IsFlat());
        return result;
    }

    bool String::MakeExternal(v8::String::ExternalStringResource* resource)
    {
        DisallowHeapAllocation no_allocation;
        // Externalizing twice leaks the external resource, so it's
        // prohibited by the API.
        DCHECK(this->SupportsExternalization());
        DCHECK(resource->IsCacheable());
#ifdef ENABLE_SLOW_DCHECKS
        if (FLAG_enable_slow_asserts) {
            // Assert that the resource and the string are equivalent.
            DCHECK(static_cast<size_t>(this->length()) == resource->length());
            ScopedVector<uc16> smart_chars(this->length());
            String::WriteToFlat(*this, smart_chars.start(), 0, this->length());
            DCHECK_EQ(0, memcmp(smart_chars.start(), resource->data(), resource->length() * sizeof(smart_chars[0])));
        }
#endif // DEBUG
        int size = this->Size(); // Byte size of the original string.
        // Abort if size does not allow in-place conversion.
        if (size < ExternalString::kUncachedSize)
            return false;
        Isolate* isolate;
        // Read-only strings cannot be made external, since that would mutate the
        // string.
        if (!GetIsolateFromWritableObject(*this, &isolate))
            return false;
        Heap* heap = isolate->heap();
        bool is_internalized = this->IsInternalizedString();
        bool has_pointers = StringShape(*this).IsIndirect();
        if (has_pointers) {
            heap->NotifyObjectLayoutChange(*this, size, no_allocation);
        }
        // Morph the string to an external string by replacing the map and
        // reinitializing the fields.  This won't work if the space the existing
        // string occupies is too small for a regular external string.  Instead, we
        // resort to an uncached external string instead, omitting the field caching
        // the address of the backing store.  When we encounter uncached external
        // strings in generated code, we need to bailout to runtime.
        Map new_map;
        ReadOnlyRoots roots(heap);
        if (size < ExternalString::kSize) {
            if (is_internalized) {
                new_map = roots.uncached_external_internalized_string_map();
            } else {
                new_map = roots.uncached_external_string_map();
            }
        } else {
            new_map = is_internalized ? roots.external_internalized_string_map()
                                      : roots.external_string_map();
        }

        // Byte size of the external String object.
        int new_size = this->SizeFromMap(new_map);
        heap->CreateFillerObjectAt(this->address() + new_size, size - new_size,
            ClearRecordedSlots::kNo);
        if (has_pointers) {
            heap->ClearRecordedSlotRange(this->address(), this->address() + new_size);
        }

        // We are storing the new map using release store after creating a filler for
        // the left-over space to avoid races with the sweeper thread.
        this->synchronized_set_map(new_map);

        ExternalTwoByteString self = ExternalTwoByteString::cast(*this);
        self->SetResource(isolate, resource);
        heap->RegisterExternalString(*this);
        if (is_internalized)
            self->Hash(); // Force regeneration of the hash value.
        return true;
    }

    bool String::MakeExternal(v8::String::ExternalOneByteStringResource* resource)
    {
        DisallowHeapAllocation no_allocation;
        // Externalizing twice leaks the external resource, so it's
        // prohibited by the API.
        DCHECK(this->SupportsExternalization());
        DCHECK(resource->IsCacheable());
#ifdef ENABLE_SLOW_DCHECKS
        if (FLAG_enable_slow_asserts) {
            // Assert that the resource and the string are equivalent.
            DCHECK(static_cast<size_t>(this->length()) == resource->length());
            if (this->IsTwoByteRepresentation()) {
                ScopedVector<uint16_t> smart_chars(this->length());
                String::WriteToFlat(*this, smart_chars.start(), 0, this->length());
                DCHECK(String::IsOneByte(smart_chars.start(), this->length()));
            }
            ScopedVector<char> smart_chars(this->length());
            String::WriteToFlat(*this, smart_chars.start(), 0, this->length());
            DCHECK_EQ(0, memcmp(smart_chars.start(), resource->data(), resource->length() * sizeof(smart_chars[0])));
        }
#endif // DEBUG
        int size = this->Size(); // Byte size of the original string.
        // Abort if size does not allow in-place conversion.
        if (size < ExternalString::kUncachedSize)
            return false;
        Isolate* isolate;
        // Read-only strings cannot be made external, since that would mutate the
        // string.
        if (!GetIsolateFromWritableObject(*this, &isolate))
            return false;
        Heap* heap = isolate->heap();
        bool is_internalized = this->IsInternalizedString();
        bool has_pointers = StringShape(*this).IsIndirect();

        if (has_pointers) {
            heap->NotifyObjectLayoutChange(*this, size, no_allocation);
        }

        // Morph the string to an external string by replacing the map and
        // reinitializing the fields.  This won't work if the space the existing
        // string occupies is too small for a regular external string.  Instead, we
        // resort to an uncached external string instead, omitting the field caching
        // the address of the backing store.  When we encounter uncached external
        // strings in generated code, we need to bailout to runtime.
        Map new_map;
        ReadOnlyRoots roots(heap);
        if (size < ExternalString::kSize) {
            new_map = is_internalized
                ? roots.uncached_external_one_byte_internalized_string_map()
                : roots.uncached_external_one_byte_string_map();
        } else {
            new_map = is_internalized
                ? roots.external_one_byte_internalized_string_map()
                : roots.external_one_byte_string_map();
        }

        // Byte size of the external String object.
        int new_size = this->SizeFromMap(new_map);
        heap->CreateFillerObjectAt(this->address() + new_size, size - new_size,
            ClearRecordedSlots::kNo);
        if (has_pointers) {
            heap->ClearRecordedSlotRange(this->address(), this->address() + new_size);
        }

        // We are storing the new map using release store after creating a filler for
        // the left-over space to avoid races with the sweeper thread.
        this->synchronized_set_map(new_map);

        ExternalOneByteString self = ExternalOneByteString::cast(*this);
        self->SetResource(isolate, resource);
        heap->RegisterExternalString(*this);
        if (is_internalized)
            self->Hash(); // Force regeneration of the hash value.
        return true;
    }

    bool String::SupportsExternalization()
    {
        if (this->IsThinString()) {
            return i::ThinString::cast(*this)->actual()->SupportsExternalization();
        }

        Isolate* isolate;
        // RO_SPACE strings cannot be externalized.
        if (!GetIsolateFromWritableObject(*this, &isolate)) {
            return false;
        }

        // Already an external string.
        if (StringShape(*this).IsExternal()) {
            return false;
        }

#ifdef V8_COMPRESS_POINTERS
        // Small strings may not be in-place externalizable.
        if (this->Size() < ExternalString::kUncachedSize)
            return false;
#else
        DCHECK_LE(ExternalString::kUncachedSize, this->Size());
#endif

        return !isolate->heap()->IsInGCPostProcessing();
    }

    void String::StringShortPrint(StringStream* accumulator, bool show_details)
    {
        const char* internalized_marker = this->IsInternalizedString() ? "#" : "";

        int len = length();
        if (len > kMaxShortPrintLength) {
            accumulator->Add("<Very long string[%s%u]>", internalized_marker, len);
            return;
        }

        if (!LooksValid()) {
            accumulator->Add("<Invalid String>");
            return;
        }

        StringCharacterStream stream(*this);

        bool truncated = false;
        if (len > kMaxShortPrintLength) {
            len = kMaxShortPrintLength;
            truncated = true;
        }
        bool one_byte = true;
        for (int i = 0; i < len; i++) {
            uint16_t c = stream.GetNext();

            if (c < 32 || c >= 127) {
                one_byte = false;
            }
        }
        stream.Reset(*this);
        if (one_byte) {
            if (show_details)
                accumulator->Add("<String[%s%u]: ", internalized_marker, length());
            for (int i = 0; i < len; i++) {
                accumulator->Put(static_cast<char>(stream.GetNext()));
            }
            if (show_details)
                accumulator->Put('>');
        } else {
            // Backslash indicates that the string contains control
            // characters and that backslashes are therefore escaped.
            if (show_details)
                accumulator->Add("<String[%s%u]\\: ", internalized_marker, length());
            for (int i = 0; i < len; i++) {
                uint16_t c = stream.GetNext();
                if (c == '\n') {
                    accumulator->Add("\\n");
                } else if (c == '\r') {
                    accumulator->Add("\\r");
                } else if (c == '\\') {
                    accumulator->Add("\\\\");
                } else if (c < 32 || c > 126) {
                    accumulator->Add("\\x%02x", c);
                } else {
                    accumulator->Put(static_cast<char>(c));
                }
            }
            if (truncated) {
                accumulator->Put('.');
                accumulator->Put('.');
                accumulator->Put('.');
            }
            if (show_details)
                accumulator->Put('>');
        }
        return;
    }

    void String::PrintUC16(std::ostream& os, int start, int end)
    { // NOLINT
        if (end < 0)
            end = length();
        StringCharacterStream stream(*this, start);
        for (int i = start; i < end && stream.HasMore(); i++) {
            os << AsUC16(stream.GetNext());
        }
    }

    // static
    Handle<String> String::Trim(Isolate* isolate, Handle<String> string,
        TrimMode mode)
    {
        string = String::Flatten(isolate, string);
        int const length = string->length();

        // Perform left trimming if requested.
        int left = 0;
        if (mode == kTrim || mode == kTrimStart) {
            while (left < length && IsWhiteSpaceOrLineTerminator(string->Get(left))) {
                left++;
            }
        }

        // Perform right trimming if requested.
        int right = length;
        if (mode == kTrim || mode == kTrimEnd) {
            while (right > left && IsWhiteSpaceOrLineTerminator(string->Get(right - 1))) {
                right--;
            }
        }

        return isolate->factory()->NewSubString(string, left, right);
    }

    bool String::LooksValid()
    {
        // TODO(leszeks): Maybe remove this check entirely, Heap::Contains uses
        // basically the same logic as the way we access the heap in the first place.
        MemoryChunk* chunk = MemoryChunk::FromHeapObject(*this);
        // RO_SPACE objects should always be valid.
        if (chunk->owner()->identity() == RO_SPACE)
            return true;
        if (chunk->heap() == nullptr)
            return false;
        return chunk->heap()->Contains(*this);
    }

    namespace {

        bool AreDigits(const uint8_t* s, int from, int to)
        {
            for (int i = from; i < to; i++) {
                if (s[i] < '0' || s[i] > '9')
                    return false;
            }

            return true;
        }

        int ParseDecimalInteger(const uint8_t* s, int from, int to)
        {
            DCHECK_LT(to - from, 10); // Overflow is not possible.
            DCHECK(from < to);
            int d = s[from] - '0';

            for (int i = from + 1; i < to; i++) {
                d = 10 * d + (s[i] - '0');
            }

            return d;
        }

    } // namespace

    // static
    Handle<Object> String::ToNumber(Isolate* isolate, Handle<String> subject)
    {
        // Flatten {subject} string first.
        subject = String::Flatten(isolate, subject);

        // Fast array index case.
        uint32_t index;
        if (subject->AsArrayIndex(&index)) {
            return isolate->factory()->NewNumberFromUint(index);
        }

        // Fast case: short integer or some sorts of junk values.
        if (subject->IsSeqOneByteString()) {
            int len = subject->length();
            if (len == 0)
                return handle(Smi::kZero, isolate);

            DisallowHeapAllocation no_gc;
            uint8_t const* data = Handle<SeqOneByteString>::cast(subject)->GetChars(no_gc);
            bool minus = (data[0] == '-');
            int start_pos = (minus ? 1 : 0);

            if (start_pos == len) {
                return isolate->factory()->nan_value();
            } else if (data[start_pos] > '9') {
                // Fast check for a junk value. A valid string may start from a
                // whitespace, a sign ('+' or '-'), the decimal point, a decimal digit
                // or the 'I' character ('Infinity'). All of that have codes not greater
                // than '9' except 'I' and &nbsp;.
                if (data[start_pos] != 'I' && data[start_pos] != 0xA0) {
                    return isolate->factory()->nan_value();
                }
            } else if (len - start_pos < 10 && AreDigits(data, start_pos, len)) {
                // The maximal/minimal smi has 10 digits. If the string has less digits
                // we know it will fit into the smi-data type.
                int d = ParseDecimalInteger(data, start_pos, len);
                if (minus) {
                    if (d == 0)
                        return isolate->factory()->minus_zero_value();
                    d = -d;
                } else if (!subject->HasHashCode() && len <= String::kMaxArrayIndexSize && (len == 1 || data[0] != '0')) {
                    // String hash is not calculated yet but all the data are present.
                    // Update the hash field to speed up sequential convertions.
                    uint32_t hash = StringHasher::MakeArrayIndexHash(d, len);
#ifdef DEBUG
                    subject->Hash(); // Force hash calculation.
                    DCHECK_EQ(static_cast<int>(subject->hash_field()),
                        static_cast<int>(hash));
#endif
                    subject->set_hash_field(hash);
                }
                return handle(Smi::FromInt(d), isolate);
            }
        }

        // Slower case.
        int flags = ALLOW_HEX | ALLOW_OCTAL | ALLOW_BINARY;
        return isolate->factory()->NewNumber(StringToDouble(isolate, subject, flags));
    }

    String::FlatContent String::GetFlatContent(
        const DisallowHeapAllocation& no_gc)
    {
        USE(no_gc);
        int length = this->length();
        StringShape shape(*this);
        String string = *this;
        int offset = 0;
        if (shape.representation_tag() == kConsStringTag) {
            ConsString cons = ConsString::cast(string);
            if (cons->second()->length() != 0) {
                return FlatContent();
            }
            string = cons->first();
            shape = StringShape(string);
        } else if (shape.representation_tag() == kSlicedStringTag) {
            SlicedString slice = SlicedString::cast(string);
            offset = slice->offset();
            string = slice->parent();
            shape = StringShape(string);
            DCHECK(shape.representation_tag() != kConsStringTag && shape.representation_tag() != kSlicedStringTag);
        }
        if (shape.representation_tag() == kThinStringTag) {
            ThinString thin = ThinString::cast(string);
            string = thin->actual();
            shape = StringShape(string);
            DCHECK(!shape.IsCons());
            DCHECK(!shape.IsSliced());
        }
        if (shape.encoding_tag() == kOneByteStringTag) {
            const uint8_t* start;
            if (shape.representation_tag() == kSeqStringTag) {
                start = SeqOneByteString::cast(string)->GetChars(no_gc);
            } else {
                start = ExternalOneByteString::cast(string)->GetChars();
            }
            return FlatContent(start + offset, length);
        } else {
            DCHECK_EQ(shape.encoding_tag(), kTwoByteStringTag);
            const uc16* start;
            if (shape.representation_tag() == kSeqStringTag) {
                start = SeqTwoByteString::cast(string)->GetChars(no_gc);
            } else {
                start = ExternalTwoByteString::cast(string)->GetChars();
            }
            return FlatContent(start + offset, length);
        }
    }

    std::unique_ptr<char[]> String::ToCString(AllowNullsFlag allow_nulls,
        RobustnessFlag robust_flag,
        int offset, int length,
        int* length_return)
    {
        if (robust_flag == ROBUST_STRING_TRAVERSAL && !LooksValid()) {
            return std::unique_ptr<char[]>();
        }
        // Negative length means the to the end of the string.
        if (length < 0)
            length = kMaxInt - offset;

        // Compute the size of the UTF-8 string. Start at the specified offset.
        StringCharacterStream stream(*this, offset);
        int character_position = offset;
        int utf8_bytes = 0;
        int last = unibrow::Utf16::kNoPreviousCharacter;
        while (stream.HasMore() && character_position++ < offset + length) {
            uint16_t character = stream.GetNext();
            utf8_bytes += unibrow::Utf8::Length(character, last);
            last = character;
        }

        if (length_return) {
            *length_return = utf8_bytes;
        }

        char* result = NewArray<char>(utf8_bytes + 1);

        // Convert the UTF-16 string to a UTF-8 buffer. Start at the specified offset.
        stream.Reset(*this, offset);
        character_position = offset;
        int utf8_byte_position = 0;
        last = unibrow::Utf16::kNoPreviousCharacter;
        while (stream.HasMore() && character_position++ < offset + length) {
            uint16_t character = stream.GetNext();
            if (allow_nulls == DISALLOW_NULLS && character == 0) {
                character = ' ';
            }
            utf8_byte_position += unibrow::Utf8::Encode(result + utf8_byte_position, character, last);
            last = character;
        }
        result[utf8_byte_position] = 0;
        return std::unique_ptr<char[]>(result);
    }

    std::unique_ptr<char[]> String::ToCString(AllowNullsFlag allow_nulls,
        RobustnessFlag robust_flag,
        int* length_return)
    {
        return ToCString(allow_nulls, robust_flag, 0, -1, length_return);
    }

    template <typename sinkchar>
    void String::WriteToFlat(String src, sinkchar* sink, int f, int t)
    {
        DisallowHeapAllocation no_gc;
        String source = src;
        int from = f;
        int to = t;
        while (true) {
            DCHECK(0 <= from && from <= to && to <= source->length());
            switch (StringShape(source).full_representation_tag()) {
            case kOneByteStringTag | kExternalStringTag: {
                CopyChars(sink, ExternalOneByteString::cast(source)->GetChars() + from,
                    to - from);
                return;
            }
            case kTwoByteStringTag | kExternalStringTag: {
                const uc16* data = ExternalTwoByteString::cast(source)->GetChars();
                CopyChars(sink, data + from, to - from);
                return;
            }
            case kOneByteStringTag | kSeqStringTag: {
                CopyChars(sink, SeqOneByteString::cast(source)->GetChars(no_gc) + from,
                    to - from);
                return;
            }
            case kTwoByteStringTag | kSeqStringTag: {
                CopyChars(sink, SeqTwoByteString::cast(source)->GetChars(no_gc) + from,
                    to - from);
                return;
            }
            case kOneByteStringTag | kConsStringTag:
            case kTwoByteStringTag | kConsStringTag: {
                ConsString cons_string = ConsString::cast(source);
                String first = cons_string->first();
                int boundary = first->length();
                if (to - boundary >= boundary - from) {
                    // Right hand side is longer.  Recurse over left.
                    if (from < boundary) {
                        WriteToFlat(first, sink, from, boundary);
                        if (from == 0 && cons_string->second() == first) {
                            CopyChars(sink + boundary, sink, boundary);
                            return;
                        }
                        sink += boundary - from;
                        from = 0;
                    } else {
                        from -= boundary;
                    }
                    to -= boundary;
                    source = cons_string->second();
                } else {
                    // Left hand side is longer.  Recurse over right.
                    if (to > boundary) {
                        String second = cons_string->second();
                        // When repeatedly appending to a string, we get a cons string that
                        // is unbalanced to the left, a list, essentially.  We inline the
                        // common case of sequential one-byte right child.
                        if (to - boundary == 1) {
                            sink[boundary - from] = static_cast<sinkchar>(second->Get(0));
                        } else if (second->IsSeqOneByteString()) {
                            CopyChars(sink + boundary - from,
                                SeqOneByteString::cast(second)->GetChars(no_gc),
                                to - boundary);
                        } else {
                            WriteToFlat(second, sink + boundary - from, 0, to - boundary);
                        }
                        to = boundary;
                    }
                    source = first;
                }
                break;
            }
            case kOneByteStringTag | kSlicedStringTag:
            case kTwoByteStringTag | kSlicedStringTag: {
                SlicedString slice = SlicedString::cast(source);
                unsigned offset = slice->offset();
                WriteToFlat(slice->parent(), sink, from + offset, to + offset);
                return;
            }
            case kOneByteStringTag | kThinStringTag:
            case kTwoByteStringTag | kThinStringTag:
                source = ThinString::cast(source)->actual();
                break;
            }
        }
    }

    template <typename SourceChar>
    static void CalculateLineEndsImpl(Isolate* isolate, std::vector<int>* line_ends,
        Vector<const SourceChar> src,
        bool include_ending_line)
    {
        const int src_len = src.length();
        for (int i = 0; i < src_len - 1; i++) {
            SourceChar current = src[i];
            SourceChar next = src[i + 1];
            if (IsLineTerminatorSequence(current, next))
                line_ends->push_back(i);
        }

        if (src_len > 0 && IsLineTerminatorSequence(src[src_len - 1], 0)) {
            line_ends->push_back(src_len - 1);
        }
        if (include_ending_line) {
            // Include one character beyond the end of script. The rewriter uses that
            // position for the implicit return statement.
            line_ends->push_back(src_len);
        }
    }

    Handle<FixedArray> String::CalculateLineEnds(Isolate* isolate,
        Handle<String> src,
        bool include_ending_line)
    {
        src = Flatten(isolate, src);
        // Rough estimate of line count based on a roughly estimated average
        // length of (unpacked) code.
        int line_count_estimate = src->length() >> 4;
        std::vector<int> line_ends;
        line_ends.reserve(line_count_estimate);
        {
            DisallowHeapAllocation no_allocation; // ensure vectors stay valid.
            // Dispatch on type of strings.
            String::FlatContent content = src->GetFlatContent(no_allocation);
            DCHECK(content.IsFlat());
            if (content.IsOneByte()) {
                CalculateLineEndsImpl(isolate, &line_ends, content.ToOneByteVector(),
                    include_ending_line);
            } else {
                CalculateLineEndsImpl(isolate, &line_ends, content.ToUC16Vector(),
                    include_ending_line);
            }
        }
        int line_count = static_cast<int>(line_ends.size());
        Handle<FixedArray> array = isolate->factory()->NewFixedArray(line_count);
        for (int i = 0; i < line_count; i++) {
            array->set(i, Smi::FromInt(line_ends[i]));
        }
        return array;
    }

    bool String::SlowEquals(String other)
    {
        DisallowHeapAllocation no_gc;
        // Fast check: negative check with lengths.
        int len = length();
        if (len != other->length())
            return false;
        if (len == 0)
            return true;

        // Fast check: if at least one ThinString is involved, dereference it/them
        // and restart.
        if (this->IsThinString() || other->IsThinString()) {
            if (other->IsThinString())
                other = ThinString::cast(other)->actual();
            if (this->IsThinString()) {
                return ThinString::cast(*this)->actual()->Equals(other);
            } else {
                return this->Equals(other);
            }
        }

        // Fast check: if hash code is computed for both strings
        // a fast negative check can be performed.
        if (HasHashCode() && other->HasHashCode()) {
#ifdef ENABLE_SLOW_DCHECKS
            if (FLAG_enable_slow_asserts) {
                if (Hash() != other->Hash()) {
                    bool found_difference = false;
                    for (int i = 0; i < len; i++) {
                        if (Get(i) != other->Get(i)) {
                            found_difference = true;
                            break;
                        }
                    }
                    DCHECK(found_difference);
                }
            }
#endif
            if (Hash() != other->Hash())
                return false;
        }

        // We know the strings are both non-empty. Compare the first chars
        // before we try to flatten the strings.
        if (this->Get(0) != other->Get(0))
            return false;

        if (IsSeqOneByteString() && other->IsSeqOneByteString()) {
            const uint8_t* str1 = SeqOneByteString::cast(*this)->GetChars(no_gc);
            const uint8_t* str2 = SeqOneByteString::cast(other)->GetChars(no_gc);
            return CompareRawStringContents(str1, str2, len);
        }

        StringComparator comparator;
        return comparator.Equals(*this, other);
    }

    bool String::SlowEquals(Isolate* isolate, Handle<String> one,
        Handle<String> two)
    {
        // Fast check: negative check with lengths.
        int one_length = one->length();
        if (one_length != two->length())
            return false;
        if (one_length == 0)
            return true;

        // Fast check: if at least one ThinString is involved, dereference it/them
        // and restart.
        if (one->IsThinString() || two->IsThinString()) {
            if (one->IsThinString())
                one = handle(ThinString::cast(*one)->actual(), isolate);
            if (two->IsThinString())
                two = handle(ThinString::cast(*two)->actual(), isolate);
            return String::Equals(isolate, one, two);
        }

        // Fast check: if hash code is computed for both strings
        // a fast negative check can be performed.
        if (one->HasHashCode() && two->HasHashCode()) {
#ifdef ENABLE_SLOW_DCHECKS
            if (FLAG_enable_slow_asserts) {
                if (one->Hash() != two->Hash()) {
                    bool found_difference = false;
                    for (int i = 0; i < one_length; i++) {
                        if (one->Get(i) != two->Get(i)) {
                            found_difference = true;
                            break;
                        }
                    }
                    DCHECK(found_difference);
                }
            }
#endif
            if (one->Hash() != two->Hash())
                return false;
        }

        // We know the strings are both non-empty. Compare the first chars
        // before we try to flatten the strings.
        if (one->Get(0) != two->Get(0))
            return false;

        one = String::Flatten(isolate, one);
        two = String::Flatten(isolate, two);

        DisallowHeapAllocation no_gc;
        String::FlatContent flat1 = one->GetFlatContent(no_gc);
        String::FlatContent flat2 = two->GetFlatContent(no_gc);

        if (flat1.IsOneByte() && flat2.IsOneByte()) {
            return CompareRawStringContents(flat1.ToOneByteVector().start(),
                flat2.ToOneByteVector().start(),
                one_length);
        } else {
            for (int i = 0; i < one_length; i++) {
                if (flat1.Get(i) != flat2.Get(i))
                    return false;
            }
            return true;
        }
    }

    // static
    ComparisonResult String::Compare(Isolate* isolate, Handle<String> x,
        Handle<String> y)
    {
        // A few fast case tests before we flatten.
        if (x.is_identical_to(y)) {
            return ComparisonResult::kEqual;
        } else if (y->length() == 0) {
            return x->length() == 0 ? ComparisonResult::kEqual
                                    : ComparisonResult::kGreaterThan;
        } else if (x->length() == 0) {
            return ComparisonResult::kLessThan;
        }

        int const d = x->Get(0) - y->Get(0);
        if (d < 0) {
            return ComparisonResult::kLessThan;
        } else if (d > 0) {
            return ComparisonResult::kGreaterThan;
        }

        // Slow case.
        x = String::Flatten(isolate, x);
        y = String::Flatten(isolate, y);

        DisallowHeapAllocation no_gc;
        ComparisonResult result = ComparisonResult::kEqual;
        int prefix_length = x->length();
        if (y->length() < prefix_length) {
            prefix_length = y->length();
            result = ComparisonResult::kGreaterThan;
        } else if (y->length() > prefix_length) {
            result = ComparisonResult::kLessThan;
        }
        int r;
        String::FlatContent x_content = x->GetFlatContent(no_gc);
        String::FlatContent y_content = y->GetFlatContent(no_gc);
        if (x_content.IsOneByte()) {
            Vector<const uint8_t> x_chars = x_content.ToOneByteVector();
            if (y_content.IsOneByte()) {
                Vector<const uint8_t> y_chars = y_content.ToOneByteVector();
                r = CompareChars(x_chars.start(), y_chars.start(), prefix_length);
            } else {
                Vector<const uc16> y_chars = y_content.ToUC16Vector();
                r = CompareChars(x_chars.start(), y_chars.start(), prefix_length);
            }
        } else {
            Vector<const uc16> x_chars = x_content.ToUC16Vector();
            if (y_content.IsOneByte()) {
                Vector<const uint8_t> y_chars = y_content.ToOneByteVector();
                r = CompareChars(x_chars.start(), y_chars.start(), prefix_length);
            } else {
                Vector<const uc16> y_chars = y_content.ToUC16Vector();
                r = CompareChars(x_chars.start(), y_chars.start(), prefix_length);
            }
        }
        if (r < 0) {
            result = ComparisonResult::kLessThan;
        } else if (r > 0) {
            result = ComparisonResult::kGreaterThan;
        }
        return result;
    }

    Object String::IndexOf(Isolate* isolate, Handle<Object> receiver,
        Handle<Object> search, Handle<Object> position)
    {
        if (receiver->IsNullOrUndefined(isolate)) {
            THROW_NEW_ERROR_RETURN_FAILURE(
                isolate, NewTypeError(MessageTemplate::kCalledOnNullOrUndefined, isolate->factory()->NewStringFromAsciiChecked("String.prototype.indexOf")));
        }
        Handle<String> receiver_string;
        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, receiver_string,
            Object::ToString(isolate, receiver));

        Handle<String> search_string;
        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, search_string,
            Object::ToString(isolate, search));

        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, position,
            Object::ToInteger(isolate, position));

        uint32_t index = receiver_string->ToValidIndex(*position);
        return Smi::FromInt(
            String::IndexOf(isolate, receiver_string, search_string, index));
    }

    namespace {

        template <typename T>
        int SearchString(Isolate* isolate, String::FlatContent receiver_content,
            Vector<T> pat_vector, int start_index)
        {
            if (receiver_content.IsOneByte()) {
                return SearchString(isolate, receiver_content.ToOneByteVector(), pat_vector,
                    start_index);
            }
            return SearchString(isolate, receiver_content.ToUC16Vector(), pat_vector,
                start_index);
        }

    } // namespace

    int String::IndexOf(Isolate* isolate, Handle<String> receiver,
        Handle<String> search, int start_index)
    {
        DCHECK_LE(0, start_index);
        DCHECK(start_index <= receiver->length());

        uint32_t search_length = search->length();
        if (search_length == 0)
            return start_index;

        uint32_t receiver_length = receiver->length();
        if (start_index + search_length > receiver_length)
            return -1;

        receiver = String::Flatten(isolate, receiver);
        search = String::Flatten(isolate, search);

        DisallowHeapAllocation no_gc; // ensure vectors stay valid
        // Extract flattened substrings of cons strings before getting encoding.
        String::FlatContent receiver_content = receiver->GetFlatContent(no_gc);
        String::FlatContent search_content = search->GetFlatContent(no_gc);

        // dispatch on type of strings
        if (search_content.IsOneByte()) {
            Vector<const uint8_t> pat_vector = search_content.ToOneByteVector();
            return SearchString<const uint8_t>(isolate, receiver_content, pat_vector,
                start_index);
        }
        Vector<const uc16> pat_vector = search_content.ToUC16Vector();
        return SearchString<const uc16>(isolate, receiver_content, pat_vector,
            start_index);
    }

    MaybeHandle<String> String::GetSubstitution(Isolate* isolate, Match* match,
        Handle<String> replacement,
        int start_index)
    {
        DCHECK_GE(start_index, 0);

        Factory* factory = isolate->factory();

        const int replacement_length = replacement->length();
        const int captures_length = match->CaptureCount();

        replacement = String::Flatten(isolate, replacement);

        Handle<String> dollar_string = factory->LookupSingleCharacterStringFromCode('$');
        int next_dollar_ix = String::IndexOf(isolate, replacement, dollar_string, start_index);
        if (next_dollar_ix < 0) {
            return replacement;
        }

        IncrementalStringBuilder builder(isolate);

        if (next_dollar_ix > 0) {
            builder.AppendString(factory->NewSubString(replacement, 0, next_dollar_ix));
        }

        while (true) {
            const int peek_ix = next_dollar_ix + 1;
            if (peek_ix >= replacement_length) {
                builder.AppendCharacter('$');
                return builder.Finish();
            }

            int continue_from_ix = -1;
            const uint16_t peek = replacement->Get(peek_ix);
            switch (peek) {
            case '$': // $$
                builder.AppendCharacter('$');
                continue_from_ix = peek_ix + 1;
                break;
            case '&': // $& - match
                builder.AppendString(match->GetMatch());
                continue_from_ix = peek_ix + 1;
                break;
            case '`': // $` - prefix
                builder.AppendString(match->GetPrefix());
                continue_from_ix = peek_ix + 1;
                break;
            case '\'': // $' - suffix
                builder.AppendString(match->GetSuffix());
                continue_from_ix = peek_ix + 1;
                break;
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9': {
                // Valid indices are $1 .. $9, $01 .. $09 and $10 .. $99
                int scaled_index = (peek - '0');
                int advance = 1;

                if (peek_ix + 1 < replacement_length) {
                    const uint16_t next_peek = replacement->Get(peek_ix + 1);
                    if (next_peek >= '0' && next_peek <= '9') {
                        const int new_scaled_index = scaled_index * 10 + (next_peek - '0');
                        if (new_scaled_index < captures_length) {
                            scaled_index = new_scaled_index;
                            advance = 2;
                        }
                    }
                }

                if (scaled_index == 0 || scaled_index >= captures_length) {
                    builder.AppendCharacter('$');
                    continue_from_ix = peek_ix;
                    break;
                }

                bool capture_exists;
                Handle<String> capture;
                ASSIGN_RETURN_ON_EXCEPTION(
                    isolate, capture, match->GetCapture(scaled_index, &capture_exists),
                    String);
                if (capture_exists)
                    builder.AppendString(capture);
                continue_from_ix = peek_ix + advance;
                break;
            }
            case '<': { // $<name> - named capture
                using CaptureState = String::Match::CaptureState;

                if (!match->HasNamedCaptures()) {
                    builder.AppendCharacter('$');
                    continue_from_ix = peek_ix;
                    break;
                }

                Handle<String> bracket_string = factory->LookupSingleCharacterStringFromCode('>');
                const int closing_bracket_ix = String::IndexOf(isolate, replacement, bracket_string, peek_ix + 1);

                if (closing_bracket_ix == -1) {
                    // No closing bracket was found, treat '$<' as a string literal.
                    builder.AppendCharacter('$');
                    continue_from_ix = peek_ix;
                    break;
                }

                Handle<String> capture_name = factory->NewSubString(replacement, peek_ix + 1, closing_bracket_ix);
                Handle<String> capture;
                CaptureState capture_state;
                ASSIGN_RETURN_ON_EXCEPTION(
                    isolate, capture,
                    match->GetNamedCapture(capture_name, &capture_state), String);

                switch (capture_state) {
                case CaptureState::INVALID:
                case CaptureState::UNMATCHED:
                    break;
                case CaptureState::MATCHED:
                    builder.AppendString(capture);
                    break;
                }

                continue_from_ix = closing_bracket_ix + 1;
                break;
            }
            default:
                builder.AppendCharacter('$');
                continue_from_ix = peek_ix;
                break;
            }

            // Go the the next $ in the replacement.
            // TODO(jgruber): Single-char lookups could be much more efficient.
            DCHECK_NE(continue_from_ix, -1);
            next_dollar_ix = String::IndexOf(isolate, replacement, dollar_string, continue_from_ix);

            // Return if there are no more $ characters in the replacement. If we
            // haven't reached the end, we need to append the suffix.
            if (next_dollar_ix < 0) {
                if (continue_from_ix < replacement_length) {
                    builder.AppendString(factory->NewSubString(
                        replacement, continue_from_ix, replacement_length));
                }
                return builder.Finish();
            }

            // Append substring between the previous and the next $ character.
            if (next_dollar_ix > continue_from_ix) {
                builder.AppendString(
                    factory->NewSubString(replacement, continue_from_ix, next_dollar_ix));
            }
        }

        UNREACHABLE();
    }

    namespace { // for String.Prototype.lastIndexOf

        template <typename schar, typename pchar>
        int StringMatchBackwards(Vector<const schar> subject,
            Vector<const pchar> pattern, int idx)
        {
            int pattern_length = pattern.length();
            DCHECK_GE(pattern_length, 1);
            DCHECK(idx + pattern_length <= subject.length());

            if (sizeof(schar) == 1 && sizeof(pchar) > 1) {
                for (int i = 0; i < pattern_length; i++) {
                    uc16 c = pattern[i];
                    if (c > String::kMaxOneByteCharCode) {
                        return -1;
                    }
                }
            }

            pchar pattern_first_char = pattern[0];
            for (int i = idx; i >= 0; i--) {
                if (subject[i] != pattern_first_char)
                    continue;
                int j = 1;
                while (j < pattern_length) {
                    if (pattern[j] != subject[i + j]) {
                        break;
                    }
                    j++;
                }
                if (j == pattern_length) {
                    return i;
                }
            }
            return -1;
        }

    } // namespace

    Object String::LastIndexOf(Isolate* isolate, Handle<Object> receiver,
        Handle<Object> search, Handle<Object> position)
    {
        if (receiver->IsNullOrUndefined(isolate)) {
            THROW_NEW_ERROR_RETURN_FAILURE(
                isolate, NewTypeError(MessageTemplate::kCalledOnNullOrUndefined, isolate->factory()->NewStringFromAsciiChecked("String.prototype.lastIndexOf")));
        }
        Handle<String> receiver_string;
        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, receiver_string,
            Object::ToString(isolate, receiver));

        Handle<String> search_string;
        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, search_string,
            Object::ToString(isolate, search));

        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, position,
            Object::ToNumber(isolate, position));

        uint32_t start_index;

        if (position->IsNaN()) {
            start_index = receiver_string->length();
        } else {
            ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, position,
                Object::ToInteger(isolate, position));
            start_index = receiver_string->ToValidIndex(*position);
        }

        uint32_t pattern_length = search_string->length();
        uint32_t receiver_length = receiver_string->length();

        if (start_index + pattern_length > receiver_length) {
            start_index = receiver_length - pattern_length;
        }

        if (pattern_length == 0) {
            return Smi::FromInt(start_index);
        }

        receiver_string = String::Flatten(isolate, receiver_string);
        search_string = String::Flatten(isolate, search_string);

        int last_index = -1;
        DisallowHeapAllocation no_gc; // ensure vectors stay valid

        String::FlatContent receiver_content = receiver_string->GetFlatContent(no_gc);
        String::FlatContent search_content = search_string->GetFlatContent(no_gc);

        if (search_content.IsOneByte()) {
            Vector<const uint8_t> pat_vector = search_content.ToOneByteVector();
            if (receiver_content.IsOneByte()) {
                last_index = StringMatchBackwards(receiver_content.ToOneByteVector(),
                    pat_vector, start_index);
            } else {
                last_index = StringMatchBackwards(receiver_content.ToUC16Vector(),
                    pat_vector, start_index);
            }
        } else {
            Vector<const uc16> pat_vector = search_content.ToUC16Vector();
            if (receiver_content.IsOneByte()) {
                last_index = StringMatchBackwards(receiver_content.ToOneByteVector(),
                    pat_vector, start_index);
            } else {
                last_index = StringMatchBackwards(receiver_content.ToUC16Vector(),
                    pat_vector, start_index);
            }
        }
        return Smi::FromInt(last_index);
    }

    bool String::IsUtf8EqualTo(Vector<const char> str, bool allow_prefix_match)
    {
        int slen = length();
        // Can't check exact length equality, but we can check bounds.
        int str_len = str.length();
        if (!allow_prefix_match && (str_len < slen || str_len > slen * static_cast<int>(unibrow::Utf8::kMaxEncodedSize))) {
            return false;
        }

        int i = 0;
        unibrow::Utf8Iterator it = unibrow::Utf8Iterator(str);
        while (i < slen && !it.Done()) {
            if (Get(i++) != *it)
                return false;
            ++it;
        }

        return (allow_prefix_match || i == slen) && it.Done();
    }

    template <>
    bool String::IsEqualTo(Vector<const uint8_t> str)
    {
        return IsOneByteEqualTo(str);
    }

    template <>
    bool String::IsEqualTo(Vector<const uc16> str)
    {
        return IsTwoByteEqualTo(str);
    }

    bool String::IsOneByteEqualTo(Vector<const uint8_t> str)
    {
        int slen = length();
        if (str.length() != slen)
            return false;
        DisallowHeapAllocation no_gc;
        FlatContent content = GetFlatContent(no_gc);
        if (content.IsOneByte()) {
            return CompareChars(content.ToOneByteVector().start(), str.start(), slen) == 0;
        }
        return CompareChars(content.ToUC16Vector().start(), str.start(), slen) == 0;
    }

    bool String::IsTwoByteEqualTo(Vector<const uc16> str)
    {
        int slen = length();
        if (str.length() != slen)
            return false;
        DisallowHeapAllocation no_gc;
        FlatContent content = GetFlatContent(no_gc);
        if (content.IsOneByte()) {
            return CompareChars(content.ToOneByteVector().start(), str.start(), slen) == 0;
        }
        return CompareChars(content.ToUC16Vector().start(), str.start(), slen) == 0;
    }

    uint32_t String::ComputeAndSetHash()
    {
        DisallowHeapAllocation no_gc;
        // Should only be called if hash code has not yet been computed.
        DCHECK(!HasHashCode());

        // Store the hash code in the object.
        uint32_t field = IteratingStringHasher::Hash(*this, HashSeed(GetReadOnlyRoots()));
        set_hash_field(field);

        // Check the hash code is there.
        DCHECK(HasHashCode());
        uint32_t result = field >> kHashShift;
        DCHECK_NE(result, 0); // Ensure that the hash value of 0 is never computed.
        return result;
    }

    bool String::ComputeArrayIndex(uint32_t* index)
    {
        int length = this->length();
        if (length == 0 || length > kMaxArrayIndexSize)
            return false;
        StringCharacterStream stream(*this);
        return StringToArrayIndex(&stream, index);
    }

    bool String::SlowAsArrayIndex(uint32_t* index)
    {
        DisallowHeapAllocation no_gc;
        if (length() <= kMaxCachedArrayIndexLength) {
            Hash(); // force computation of hash code
            uint32_t field = hash_field();
            if ((field & kIsNotArrayIndexMask) != 0)
                return false;
            // Isolate the array index form the full hash field.
            *index = ArrayIndexValueBits::decode(field);
            return true;
        } else {
            return ComputeArrayIndex(index);
        }
    }

    void String::PrintOn(FILE* file)
    {
        int length = this->length();
        for (int i = 0; i < length; i++) {
            PrintF(file, "%c", Get(i));
        }
    }

    Handle<String> SeqString::Truncate(Handle<SeqString> string, int new_length)
    {
        if (new_length == 0)
            return string->GetReadOnlyRoots().empty_string_handle();

        int new_size, old_size;
        int old_length = string->length();
        if (old_length <= new_length)
            return string;

        if (string->IsSeqOneByteString()) {
            old_size = SeqOneByteString::SizeFor(old_length);
            new_size = SeqOneByteString::SizeFor(new_length);
        } else {
            DCHECK(string->IsSeqTwoByteString());
            old_size = SeqTwoByteString::SizeFor(old_length);
            new_size = SeqTwoByteString::SizeFor(new_length);
        }

        int delta = old_size - new_size;

        Address start_of_string = string->address();
        DCHECK(IsAligned(start_of_string, kObjectAlignment));
        DCHECK(IsAligned(start_of_string + new_size, kObjectAlignment));

        Heap* heap = Heap::FromWritableHeapObject(*string);
        // Sizes are pointer size aligned, so that we can use filler objects
        // that are a multiple of pointer size.
        heap->CreateFillerObjectAt(start_of_string + new_size, delta,
            ClearRecordedSlots::kNo);
        // We are storing the new length using release store after creating a filler
        // for the left-over space to avoid races with the sweeper thread.
        string->synchronized_set_length(new_length);

        return string;
    }

    void SeqOneByteString::clear_padding()
    {
        int data_size = SeqString::kHeaderSize + length() * kOneByteSize;
        memset(reinterpret_cast<void*>(address() + data_size), 0,
            SizeFor(length()) - data_size);
    }

    void SeqTwoByteString::clear_padding()
    {
        int data_size = SeqString::kHeaderSize + length() * kUC16Size;
        memset(reinterpret_cast<void*>(address() + data_size), 0,
            SizeFor(length()) - data_size);
    }

    uint16_t ConsString::ConsStringGet(int index)
    {
        DCHECK(index >= 0 && index < this->length());

        // Check for a flattened cons string
        if (second()->length() == 0) {
            String left = first();
            return left->Get(index);
        }

        String string = String::cast(*this);

        while (true) {
            if (StringShape(string).IsCons()) {
                ConsString cons_string = ConsString::cast(string);
                String left = cons_string->first();
                if (left->length() > index) {
                    string = left;
                } else {
                    index -= left->length();
                    string = cons_string->second();
                }
            } else {
                return string->Get(index);
            }
        }

        UNREACHABLE();
    }

    uint16_t ThinString::ThinStringGet(int index) { return actual()->Get(index); }

    uint16_t SlicedString::SlicedStringGet(int index)
    {
        return parent()->Get(offset() + index);
    }

    int ExternalString::ExternalPayloadSize() const
    {
        int length_multiplier = IsTwoByteRepresentation() ? i::kShortSize : kCharSize;
        return length() * length_multiplier;
    }

    FlatStringReader::FlatStringReader(Isolate* isolate, Handle<String> str)
        : Relocatable(isolate)
        , str_(str.location())
        , length_(str->length())
    {
        PostGarbageCollection();
    }

    FlatStringReader::FlatStringReader(Isolate* isolate, Vector<const char> input)
        : Relocatable(isolate)
        , str_(nullptr)
        , is_one_byte_(true)
        , length_(input.length())
        , start_(input.start())
    {
    }

    void FlatStringReader::PostGarbageCollection()
    {
        if (str_ == nullptr)
            return;
        Handle<String> str(str_);
        DCHECK(str->IsFlat());
        DisallowHeapAllocation no_gc;
        // This does not actually prevent the vector from being relocated later.
        String::FlatContent content = str->GetFlatContent(no_gc);
        DCHECK(content.IsFlat());
        is_one_byte_ = content.IsOneByte();
        if (is_one_byte_) {
            start_ = content.ToOneByteVector().start();
        } else {
            start_ = content.ToUC16Vector().start();
        }
    }

    void ConsStringIterator::Initialize(ConsString cons_string, int offset)
    {
        DCHECK(!cons_string.is_null());
        root_ = cons_string;
        consumed_ = offset;
        // Force stack blown condition to trigger restart.
        depth_ = 1;
        maximum_depth_ = kStackSize + depth_;
        DCHECK(StackBlown());
    }

    String ConsStringIterator::Continue(int* offset_out)
    {
        DCHECK_NE(depth_, 0);
        DCHECK_EQ(0, *offset_out);
        bool blew_stack = StackBlown();
        String string;
        // Get the next leaf if there is one.
        if (!blew_stack)
            string = NextLeaf(&blew_stack);
        // Restart search from root.
        if (blew_stack) {
            DCHECK(string.is_null());
            string = Search(offset_out);
        }
        // Ensure future calls return null immediately.
        if (string.is_null())
            Reset(ConsString());
        return string;
    }

    String ConsStringIterator::Search(int* offset_out)
    {
        ConsString cons_string = root_;
        // Reset the stack, pushing the root string.
        depth_ = 1;
        maximum_depth_ = 1;
        frames_[0] = cons_string;
        const int consumed = consumed_;
        int offset = 0;
        while (true) {
            // Loop until the string is found which contains the target offset.
            String string = cons_string->first();
            int length = string->length();
            int32_t type;
            if (consumed < offset + length) {
                // Target offset is in the left branch.
                // Keep going if we're still in a ConString.
                type = string->map()->instance_type();
                if ((type & kStringRepresentationMask) == kConsStringTag) {
                    cons_string = ConsString::cast(string);
                    PushLeft(cons_string);
                    continue;
                }
                // Tell the stack we're done descending.
                AdjustMaximumDepth();
            } else {
                // Descend right.
                // Update progress through the string.
                offset += length;
                // Keep going if we're still in a ConString.
                string = cons_string->second();
                type = string->map()->instance_type();
                if ((type & kStringRepresentationMask) == kConsStringTag) {
                    cons_string = ConsString::cast(string);
                    PushRight(cons_string);
                    continue;
                }
                // Need this to be updated for the current string.
                length = string->length();
                // Account for the possibility of an empty right leaf.
                // This happens only if we have asked for an offset outside the string.
                if (length == 0) {
                    // Reset so future operations will return null immediately.
                    Reset(ConsString());
                    return String();
                }
                // Tell the stack we're done descending.
                AdjustMaximumDepth();
                // Pop stack so next iteration is in correct place.
                Pop();
            }
            DCHECK_NE(length, 0);
            // Adjust return values and exit.
            consumed_ = offset + length;
            *offset_out = consumed - offset;
            return string;
        }
        UNREACHABLE();
    }

    String ConsStringIterator::NextLeaf(bool* blew_stack)
    {
        while (true) {
            // Tree traversal complete.
            if (depth_ == 0) {
                *blew_stack = false;
                return String();
            }
            // We've lost track of higher nodes.
            if (StackBlown()) {
                *blew_stack = true;
                return String();
            }
            // Go right.
            ConsString cons_string = frames_[OffsetForDepth(depth_ - 1)];
            String string = cons_string->second();
            int32_t type = string->map()->instance_type();
            if ((type & kStringRepresentationMask) != kConsStringTag) {
                // Pop stack so next iteration is in correct place.
                Pop();
                int length = string->length();
                // Could be a flattened ConsString.
                if (length == 0)
                    continue;
                consumed_ += length;
                return string;
            }
            cons_string = ConsString::cast(string);
            PushRight(cons_string);
            // Need to traverse all the way left.
            while (true) {
                // Continue left.
                string = cons_string->first();
                type = string->map()->instance_type();
                if ((type & kStringRepresentationMask) != kConsStringTag) {
                    AdjustMaximumDepth();
                    int length = string->length();
                    if (length == 0)
                        break; // Skip empty left-hand sides of ConsStrings.
                    consumed_ += length;
                    return string;
                }
                cons_string = ConsString::cast(string);
                PushLeft(cons_string);
            }
        }
        UNREACHABLE();
    }

    template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE) void String::WriteToFlat(
        String source, uint16_t* sink, int from, int to);

} // namespace internal
} // namespace v8
